package Demo1;

public class GetIntersectionNode {
    class ListNode {
       int val;
       ListNode next;
       ListNode(int x) {
           val = x;
           next = null;
       }
   }

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode pLong = headA;
        ListNode pShort = headB;

        //求长度
        int lenLong = 0;
        while (pLong != null){
            lenLong++;
            pLong = pLong.next;
        }

        int lenShort = 0;
        while (pShort != null){
            lenShort++;
            pShort = pShort.next;
        }

        //判断真的长短链表
        if (lenShort > lenLong){
            pShort = headA;
            pLong = headB;
        }else{
            pLong = headA;
            pShort = headB;
        }

        int n = lenLong > lenShort?lenLong - lenShort:lenShort - lenLong;
        ListNode fast = pLong;
        ListNode slow = pShort;
        for (int i = 0; i < n; i++){
            fast = fast.next;
        }

        while (fast != slow){
            fast = fast.next;
            slow = slow.next;
        }

        return fast;
    }


    public ListNode creatList1(){
        ListNode node1 = new ListNode(4);
        ListNode node2 = new ListNode(1);
        ListNode node3 = new ListNode(8);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = null;

        return node1;
    }
    public ListNode creatList2(){
        ListNode node1 = new ListNode(5);
        ListNode node2 = new ListNode(6);
        ListNode node3 = new ListNode(1);
        ListNode node4 = new ListNode(8);
        ListNode node5 = new ListNode(4);
        ListNode node6 = new ListNode(5);

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node6;
        node6.next = null;

        return node1;
    }

    public static void main(String[] args) {
        GetIntersectionNode getIntersectionNode1 = new GetIntersectionNode();
        getIntersectionNode1.getIntersectionNode(getIntersectionNode1.creatList1(),getIntersectionNode1.creatList2());
    }
}
